import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-11
 * Time: 12:41
 */

class Solution1 {
    public int countNegatives(int[][] grid) {
        int i =0;//0行
        int j =grid[0].length-1;//最后一列
        int cnt =0;
        //每个数字都与tmp比较，如果比tmp小那就记录个数累加起来
        while(i<grid.length&&j>=0){
            if(grid[i][j]<0){
                //如果最右上角的元素小于0证明这一列都小于0，然后累加个数，然后去掉这一列
                cnt+=grid.length-i;
                --j;
            }else {
                //否则的话这个元素大于0，而这个元素是递减的元素，此元素是这一行当中最小的，
                //所以这个元素前面的元素也都是大于0的所以不符合，我们就去掉这一行
                ++i;
            }
        }
        return cnt;
    }
}

class Solution {
    // 二分O(mlogn)
    public int countNegatives(int[][] grid) {
        int res = 0;
        // 遍历每一行
        for (int i = 0; i < grid.length; i++) {
            int left = 0, right = grid[0].length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (grid[i][mid] >= 0) {
                    // 向右找
                    left = mid + 1;
                } else {
                    // 找到最左边的负数
                    right = mid;
                }
            }
            if (grid[i][left] < 0) {
                res += grid[0].length - left;
            }
        }
        return res;
    }
}
public class TestLeetCode {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {{4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3}};
        int[] array = grid[0];
        for(int num: array){
            System.out.println(num);
        }
        solution.countNegatives(grid);
    }

}
